package com.ly.algorithm.leetcode.heap;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Classname Problem703
 * @Description
 *
 * 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
 *
 * 请实现 KthLargest 类：
 *
 * KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
 * int add(int val) 返回当前数据流中第 k 大的元素。
 *
 *
 * @Date 2020/12/19 18:29
 * @Author 冷心影翼
 */
public class Problem703 {

	public static void main(String[] args) {
		KthLargest kthLargest = new KthLargest(3,new int[]{4,5,8,2});
		System.out.println(kthLargest.add(3));
		System.out.println(kthLargest.add(5));
		System.out.println(kthLargest.add(10));
		System.out.println(kthLargest.add(9));
		System.out.println(kthLargest.add(4));
		// 4 5 8
		//  5 5 8
		//  5 8 10
		// 8 9 10
		// 8 9 10
	}
}

class KthLargest {

	PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

	int k;

	public KthLargest(int k, int[] nums) {
		this.k = k;
		for(int i=0;i<nums.length;i++) {
			priorityQueue.add(nums[i]);
		}
	}

	public int add(int val) {
		priorityQueue.add(val);
		while (priorityQueue.size() > k) {
			priorityQueue.poll();
		}
		return priorityQueue.peek();
	}
}
